import java.io.*;
import java.util.StringTokenizer;

public class 金明的预算方案 {
    public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static Read in = new Read();
    public static int MAXN = 32001;
    public static int MAXM = 61;
    public static boolean[] kings = new boolean[MAXM]; // 判断是否是主键
    public static int[] cost = new int[MAXM]; // 价钱
    public static int[] val = new int[MAXM]; // 重要性

    public static int[] fans = new int[MAXM]; // 每个主件是否存在附件, 存储有几个
    public static int[][] follows = new int[MAXM][2]; // 存储主键的两个附件的号数

    public static void main(String[] args) throws IOException {
        int n = in.nextInt();
        int m = in.nextInt();
        for (int i = 1; i <= m; i++) {
           int v = in.nextInt();
           int p = in.nextInt();
           int q = in.nextInt();
           cost[i] = v;
           val[i] = v * p;
           kings[i] = q == 0;
           if (q != 0) {
               follows[q][fans[q]++] = i;
           }
        }
        int p = 0;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            // 是主件
            if (kings[i]) {
                for (int j = 0; j <= n; j++) {
                    // 不买主件
                    dp[i][j] = dp[p][j];
                    // 买一个主件
                    if (j - cost[i] >= 0) {
                        dp[i][j] = Math.max(dp[p][j - cost[i]] + val[i],dp[i][j]);
                    }
                    // 买一个主件 ＋ 第一个附件
                    if (fans[i] >= 1 && j - cost[i] - cost[follows[i][0]] >= 0) {
                        dp[i][j] = Math.max(dp[p][j - cost[i] - cost[follows[i][0]]] + val[i] + val[follows[i][0]],dp[i][j]);
                    }
                    // 买一个主件 + 两个附件
                    if (fans[i] >= 2 && j - cost[i] - cost[follows[i][0]] - cost[follows[i][1]] >= 0) {
                        dp[i][j] = Math.max(dp[p][j - cost[i] - cost[follows[i][0]] - cost[follows[i][1]]] + val[i] + val[follows[i][0]] + val[follows[i][1]],dp[i][j]);
                    }
                    // 买一个主件 + 第二个附件
                    if (fans[i] >= 2 && j - cost[i] - cost[follows[i][1]] >= 0) {
                        dp[i][j] = Math.max(dp[p][j - cost[i] - cost[follows[i][1]]] + val[i] + val[follows[i][1]],dp[i][j]);
                    }
                }
                p = i;

            }
        }
        System.out.println(dp[p][n]);
    }




    public static class Read {
        StringTokenizer st = new StringTokenizer("");
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String next() throws IOException {
            while (!st.hasMoreTokens()) {
                st = new StringTokenizer(bf.readLine());
            }
            return st.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}
